# 二叉树的python实现
class Node:
    def __init__(self,item):
        self.item=item
        self.lnode=None
        self.rnode=None

class Tree:
    def __init__(self,node):
        if isinstance(node,Node):
            self.__head=node
        else:
            self.__head=None
    def getRoot(self):
        return self.__head
    def addNode(self,item):
        # 向二叉树中添加元素
        newNode=Node(item)
        if self.__head==None:
            self.__head=newNode
        else:
            queue=[]
            queue.append(self.__head)
            while queue!=[]:
                curNode=queue.pop(0)
                if curNode.lnode==None:
                    curNode.lnode=newNode
                    break
                else:
                    queue.append(curNode.lnode)
                if curNode.rnode==None:
                    curNode.rnode=newNode
                    break
                else:
                    queue.append(curNode.rnode)
    def travelWidth(self):
        # 广度优先遍历
        queue=[]
        queue.append(self.__head)
        while queue!=[]:
            curNode=queue.pop(0)
            if curNode.lnode!=None:
                queue.append(curNode.lnode)
            if curNode.rnode!=None:
                queue.append(curNode.rnode)
            print(curNode.item,end='\t')
    def travelBefore(self,root):
        if root==None:
            return
        else:
            print(root.item,end='\t')
            if root.lnode!=None:
                self.travelBefore(root.lnode)
            if root.rnode!=None:
                self.travelBefore(root.rnode)
    def travelMid(self,root):
        if root==None:
            return
        else:
            if root.lnode!=None:
                self.travelMid(root.lnode)
            print(root.item,end='\t')
            if root.rnode!=None:
                self.travelMid(root.rnode)
    def travelAfter(self,root):
        if root==None:
            return
        else:
            if root.lnode!=None:
                self.travelAfter(root.lnode)
            if root.rnode!=None:
                self.travelAfter(root.rnode)
            print(root.item,end='\t')
if __name__=="__main__":
    mytree=Tree(15)
    mytree.addNode(12)
    mytree.addNode(13)
    mytree.addNode(14)
    mytree.addNode(15)
    mytree.addNode(16)
    print("广度优先遍历")
    mytree.travelWidth()
    print("\n深度优先遍历")
    print("先序遍历")
    mytree.travelBefore(mytree.getRoot())
    print("\n中序遍历")
    mytree.travelMid(mytree.getRoot())
    print("\n后序遍历")
    mytree.travelAfter(mytree.getRoot())